import numpy as np
import math
import random

def simulated_annealing(values, weights, max_weight, max_temperature=100, cooling_rate=0.99):
    num_items = len(values)
    current_solution = generate_random_solution(num_items)
    current_value = calculate_total(current_solution, values)
    best_solution = np.copy(current_solution)
    best_value = current_value

    temperature = max_temperature

    while temperature > 1:

        neighbor_solution = generate_neighbor_solution(current_solution)
        neighbor_value = calculate_total(neighbor_solution, values)
        neighbor_weight = calculate_total(neighbor_solution, weights)

        # 如果新解的重量超过了最大重量，则跳过
        if neighbor_weight > max_weight:
            continue

        if accept_solution(current_value, neighbor_value, temperature):
            current_solution = np.copy(neighbor_solution)
            current_value = neighbor_value

            if current_value > best_value:
                best_solution = np.copy(current_solution)
                best_value = current_value
        temperature *= cooling_rate

    return best_solution, best_value

def generate_random_solution(num_items):
    return np.random.randint(2, size=num_items)

def generate_neighbor_solution(solution):
    neighbor_solution = np.copy(solution)
    index_to_flip = np.random.randint(len(solution))
    neighbor_solution[index_to_flip] = 1 - neighbor_solution[index_to_flip]
    return neighbor_solution

def accept_solution(current_value, neighbor_value, temperature):
    if neighbor_value > current_value:
        return True
    else:
        probability = math.exp((neighbor_value - current_value) / temperature)
        return random.uniform(0, 1) < probability

def calculate_total(solution, values):
    return np.sum(solution * values)


# 示例输入数据
values = np.array([10, 40, 30, 50])
weights = np.array([5, 4, 6, 3])
max_weight = 10

# 调用模拟退火算法解决01背包问题
best_solution, best_value = simulated_annealing(values, weights, max_weight)

# 输出结果
print("Best Solution:", best_solution)
print("Best Value:", best_value)
